package gold.digger;

import gold.utils.InputUtil;
import gold.vo.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC919 {
    public long startExecuteTime = System.currentTimeMillis();


    class CBTInserter {

        int curDepth = 0;
        TreeNode ctRoot;
        Deque<TreeNode> curLayer = new LinkedList<>();
        Deque<TreeNode> lastLayer = new LinkedList<>();

        public CBTInserter(TreeNode root) {
            ctRoot = new TreeNode(root.val);
            curLayer.push(ctRoot);
            Deque<TreeNode> travelQueue = new LinkedList<>();
            if (null != root.left) travelQueue.addLast(root.left);
            if (null != root.right) travelQueue.addLast(root.right);
            while (!travelQueue.isEmpty()) {
                TreeNode cur = travelQueue.pollFirst();
                insert(cur.val);
                if (null != cur.left) travelQueue.addLast(cur.left);
                if (null != cur.right) travelQueue.addLast(cur.right);
            }
        }

        public int insert(int val) {
            if (curLayer.size() == (int) (Math.pow(2, curDepth))) {
                // current need to reverse layer
                lastLayer.clear();
                Deque<TreeNode> temp = lastLayer;
                lastLayer = curLayer;
                curLayer = temp;
                ++curDepth;
            }

            TreeNode cur = new TreeNode(val);
            curLayer.addLast(cur);
            if (lastLayer.peekFirst().left != null && lastLayer.peekFirst().right != null) lastLayer.pollFirst();
            if (lastLayer.peekFirst().left == null) lastLayer.peekFirst().left = cur;
            else if (lastLayer.peekFirst().right == null) lastLayer.peekFirst().right = cur;
            return lastLayer.peekFirst().val;
        }

        public TreeNode get_root() {
            return ctRoot;
        }
    }

    public void run() {
//        CBTInserter cBTInserter = new CBTInserter(TreeNode.createTree("[1,2]"));
//        System.out.println(cBTInserter.insert(3));  // 返回 1
//        System.out.println(cBTInserter.insert(4));  // 返回 2
//        System.out.println(cBTInserter.get_root());     // 返回 [1, 2, 3, 4]


        CBTInserter cBTInserter = new CBTInserter(TreeNode.createTree("[1,2,3,4,5,6]"));
        System.out.println(cBTInserter.insert(7));  // 返回 1
        System.out.println(cBTInserter.insert(8));  // 返回 2
        System.out.println(cBTInserter.get_root());     // 返回 [1, 2, 3, 4]

    }

    public static void main(String[] args) throws Exception {
        LC919 an = new LC919();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
